package com.gwcloud.leetcode.tags.dp;

/** 
* @ClassName   : Leetcode0516 
* @author      : ganwei 
* @date        : 2020年5月16日 
* @Description : 516. 最长回文子序列 
*/
public class Leetcode0516 {
    /**
     * -解题思路，动态规划
     */
	public int longestPalindromeSubseq(String s) {
		int n = s.length();
		int[][] dp = new int[n][n];
		//base case
		for(int i = 0; i < n; i++) {
			dp[i][i] = 1;
		}
		
		for(int i = n-1; i >= 0; i--) {
			for(int j = i+1; j < n; j++) {
				if(s.charAt(i) == s.charAt(j)) {
					dp[i][j] = dp[i+1][j-1] + 2;
				}else {
					dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
				}
			}
		}
		
		return dp[0][n-1];
    }
    
	/**
	 * -主函数
	 */
    public static void main(String[] args) {
    	Leetcode0516 l0516 = new Leetcode0516();
    	System.out.println(l0516.longestPalindromeSubseq("cbbd"));
    }
}
